//v3版本，   10 万个元素 5 万次操作 合并时间：3.912 ms 查找时间：0.9301 ms
//           1 万个元素  0.5 万次操作 合并时间：0.8569 ms 查找时间：0.8176 ms   
public class union_find_v3 extends union_find_v0{
    public int weight[];
    public union_find_v3(int number)
    {
        super(number);
        weight=new int[number];
        for(int i=0;i<number;i++)  //初始化
        {
         weight[i]=1;
        } 
    }

    public int root(int a)
    {
        int i=a;
        while(true)
        {
        if(i==this.a[i])
        {
            return i;
        }
        else
        {
            i=this.a[i];
        }
    }
    }
    public boolean connected(int a,int b)
    {
        if(a>this.a.length||b>this.a.length)
        {
            System.out.printf("输入越界！");
            return true;
        }
        return (root(a)==root(b));
    }
    public void union(int a,int b)
    {
        int root_a=root(a);
        int root_b=root(b);
        if(root_a==root_b)
        {
            return ;
        }
        else
        {
            if(weight[root_a]>=weight[root_b])
            {
               this.a[root_b]=root_a;
               weight[root_a]+=weight[root_b];  
            }
            else
            {
                this.a[root_a]=root_b;
                weight[root_b]+=weight[root_a];  
            } 
        }
    }
}
